(՞˶･֊･˶՞)
嗨，我是wec，今天是DAY 17。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一個包含n個整數的數組nums和一個目標值target，判斷nums中是否存在四個數字，使它們的和等於target。找出所有不重複的四元組(a, b, c, d)。

🔎 解題思路＆程式碼

1️⃣ 雙指針

第1步： 先對nums做排序。
第2步： 使用兩層循環，第一層選擇基準數a，第二層選擇b。每次確定a和b之後，將問題轉化為「兩數之和」，使用雙指針left和right在剩下的數組中尋找c和d。如果找到符合條件的組合(a, b, c, d)就記錄下來。
第3步： 跳過與前一個數字相同的基準數，避免產生重複的組合。
程式碼：

def four_sum(nums, target)
  nums.sort!
  result = []

  (0...nums.length).each do |i|
    next if i > 0 && nums[i] == nums[i - 1]

    (i + 1...nums.length).each do |j|
      next if j > i + 1 && nums[j] == nums[j - 1]

      left, right = j + 1, nums.length - 1

      while left < right
        sum = nums[i] + nums[j] + nums[left] + nums[right]

        if sum == target
          result << [nums[i], nums[j], nums[left], nums[right]]
          left += 1 while left < right && nums[left] == nums[left - 1]
          right -= 1 while left < right && nums[right] == nums[right + 1]
          left += 1
          right -= 1
        elsif sum < target
          left += 1
        else
          right -= 1
        end
      end
    end
  end

  result
end

🔎 總結

時間複雜度

雙指針： 時間複雜度為O(n³)，n為組數長度。
➡️ 這題和3Sum類似，關鍵在於排序後利用雙指針來縮小搜尋範圍，避免用四層循環暴力解題。透過排序和雙指針，可以在O(n³)的時間內解決這個問題，比起直接暴力的O(n⁴)方式要高效很多。

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃維他命c軟糖。
明天要說：Ruby精選刷題！Medium路跑D-10(>∀･)⌒☆